package com.itheima.leetcode.od.b.dynamicprogramming.bitwise;

import java.util.Arrays;

/**
 * (A卷,200分)- 不含101的数（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 小明在学习二进制时，发现了一类不含 101的数，也就是：
 * <p>
 * 将数字用二进制表示，不能出现 101 。
 * 现在给定一个整数区间 [l,r] ，请问这个区间包含了多少个不含 101 的数？
 * <p>
 * 输入描述
 * <p>
 * 输入的唯一一行包含两个正整数 l， r（ 1 ≤ l ≤ r ≤ 10^9）。
 * <p>
 * 输出描述
 * <p>
 * 输出的唯一一行包含一个整数，表示在 [l,r] 区间内一共有几个不含 101 的数。
 * <p>
 * 用例
 * <p>
 * 输入	1 10
 * 输出	8
 * 说明	区间 [1,10] 内， 5 的二进制表示为 101 ，10的二进制表示为 1010 ，因此区间 [ 1 , 10 ] 内有 10−2=8 个不含 101的数。
 * <p>
 * 输入	10 20
 * 输出	7
 * 说明	区间 [10,20] 内，满足条件的数字有 [12,14,15,16,17,18,19] 因此答案为 7。
 */
public class NumbersExcluding101 {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int L = sc.nextInt();
        int R = sc.nextInt();*/

        int L = 1;
        int R = 10;

        int count = digitSearch(R) - digitSearch(L - 1);
        System.out.println(count);
    }

    /**
     * 建议参考文档<a href="https://lfool.github.io/LFool-Notes/algorithm/%E6%95%B0%E4%BD%8DDP.html"><b>数位DP</b></a>，但是作者 <b>状态复用</b> 那一块写的有点瑕疵，很容易让人误解
     *
     * @param num
     * @return
     */
    public static int digitSearch(int num) {
        Integer[] arr = Arrays.stream(Integer.toBinaryString(num).split(""))
                .map(Integer::parseInt)
                .toArray(Integer[]::new);

        int[][][] f = new int[arr.length][2][2];

        return dfs(0, true, f, arr, 0, 0);
    }

    /**
     * 按位遍历
     *
     * @param p
     * @param limit
     * @param f
     * @param arr
     * @param pre
     * @param prepre
     * @return
     */
    public static int dfs(int p, boolean limit, int[][][] f, Integer[] arr, int pre, int prepre) {
        if (p == arr.length) {
            return 1;
        }

        if (!limit && f[p][pre][prepre] != 0) {
            return f[p][pre][prepre];
        }

        int max = limit ? arr[p] : 1;
        int count = 0;

        for (int i = 0; i <= max; i++) {
            if (i == 1 && pre == 0 && prepre == 1) {
                continue;
            }
            count += dfs(p + 1, limit && i == max, f, arr, i, pre);
        }

        if (!limit) {
            f[p][pre][prepre] = count;
        }

        return count;
    }
}